//
// Created by 许欣鑫 on 25-3-28.
//

#ifndef SOLUTION_3_1_H
#define SOLUTION_3_1_H
#include <vector>
#include <bitset>

#include "solution_1_2.h"
using namespace std;

class Solution_3_1 {
public:
    //和为目标值的最长子序列的长度  https://leetcode.cn/problems/length-of-the-longest-subsequence-that-sums-to-target/
    int lengthOfLongestSubsequenceDFS(vector<int> &nums, int target) {
        int max_len = -1;
        // 递归函数，用于计算子序列的和与长度
        function<int(int, int, int)> dfs = [&](int index, int current_sum, int current_length) -> int {
            // 如果当前和已经等于目标值
            if (current_sum == target) {
                return current_length;
            }
            // 如果遍历到数组的末尾
            if (index >= nums.size()) {
                return -1;
            }
            // 不选择当前元素
            int max_len_without = dfs(index + 1, current_sum, current_length);
            // 选择当前元素（如果和没有超过目标）
            int max_len_with = -1;
            if (current_sum + nums[index] <= target) {
                max_len_with = dfs(index + 1, current_sum + nums[index], current_length + 1);
            }
            // 返回最大长度
            return max(max_len_without, max_len_with);
        };
        max_len = dfs(0, 0, 0); // 从第0个元素开始，当前和为0，当前长度为0
        return max_len;
    }

    //总之就是选与不选 dp[i][j] i = index j=current_sum   dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i-1]]+1)
    int lengthOfLongestSubsequenceDP(vector<int> &nums, int target) {
        int n = nums.size();
        vector<vector<int> > dp(n + 1, vector<int>(target + 1, INT_MIN));
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - nums[i - 1] >= 0 && dp[i - 1][j - nums[i - 1]] != INT_MIN) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i - 1]] + 1);
                }
            }
        }
        return dp[n][target] == INT_MIN ? -1 : dp[n][target];
    }

    int lengthOfLongestSubsequenceDPLessM(vector<int> &nums, int target) {
        int n = nums.size();
        vector<int> dp(target + 1, INT_MIN);
        dp[0] = 0;
        // 填充 DP 数组
        for (int i = 0; i < n; ++i) {
            // 必须从后往前遍历，防止当前状态影响到后续状态
            for (int s = target; s >= nums[i]; --s) {
                // 选择当前元素
                if (dp[s - nums[i]] != INT_MIN) {
                    dp[s] = max(dp[s], dp[s - nums[i]] + 1);
                }
            }
        }
        return dp[target] == INT_MIN ? -1 : dp[target];
    }

    //分割等和子集 https://leetcode.cn/problems/partition-equal-subset-sum/description/
    //依旧是01问题,每个元素加入左边还是加入右边,算出其中的一半,i为index,j为sum,dp[i][j]=dp[i-1][j-nums[i]]>0?1:-1
    //如果不关心i的顺序,只需要dp[i]=dp[i] || dp[i-num] num为nums中的元素
    bool canPartition(vector<int> &nums) {
        int sum = 0;
        for (int num: nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int num: nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }

        return dp[target];
    }

    //可以使用bitmap进行优化 bitmap适用于表示01状态的转化
    bool canPartitionBitMap(vector<int> &nums) {
        int sum = 0;
        for (int num: nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        bitset<10001> bits(1);
        for (int num: nums) {
            bits |= (bits << num);
        }
        return bits[target];
    }

    //目标和  https://leetcode.cn/problems/target-sum/description/
    int findTargetSumWays(vector<int> &nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (abs(target) > sum) return 0;
        vector<int> dp(2001, 0);
        constexpr int offset = 1000;
        int left = offset - abs(nums[0]);
        int right = offset + abs(nums[0]);
        // dp[left] = 1;
        // dp[right] = 1;
        // 处理第一个数字，特别注意 0 的情况
        if (nums[0] == 0) {
            dp[offset] = 2; // +0 和 -0 两种方式
        } else {
            dp[offset + nums[0]] = 1;
            dp[offset - nums[0]] = 1;
        }
        //直接更改会出错
        for (int i = 1; i < nums.size(); ++i) {
            vector<int> next_dp(2001, 0);
            for (int j = left; j <= right; ++j) {
                if (dp[j] > 0) {
                    next_dp[j + nums[i]] += dp[j];
                    next_dp[j - nums[i]] += dp[j];
                }
            }
            left -= abs(nums[i]);
            right += abs(nums[i]);
            dp = next_dp;
        }
        return dp[target + offset];
    }
    // int findTargetSumWaysLessSpace(vector<int> &nums, int target) {
    //     int sum = accumulate(nums.begin(), nums.end(), 0);
    //     if (abs(target) > sum) return 0;
    //     vector<int> dp(2001, 0);
    //     constexpr int offset = 1000;
    //
    //     // 特别处理第一个数字
    //     if (nums[0] == 0) {
    //         dp[offset] = 2; // +0 和 -0 两种方式
    //     } else {
    //         dp[offset + nums[0]] = 1;
    //         dp[offset - nums[0]] = 1;
    //     }
    //
    //     // 从第二个数字开始更新 dp 数组
    //     for (int i = 1; i < nums.size(); ++i) {
    //         // 从右到左更新 dp 数组，避免影响当前数字的更新
    //         for (int j = 2000 - abs(nums[i]); j >= 0; --j) {
    //             if (dp[j] > 0) {
    //                 dp[j + nums[i]] += dp[j];
    //                 dp[j - nums[i]] += dp[j];
    //             }
    //         }
    //     }
    //
    //     return dp[target + offset];
    // }

    //将一个数字表示成幂的和的方案数 https://leetcode.cn/problems/ways-to-express-an-integer-as-sum-of-powers/description/
    int numberOfWays(int n, int x) {
        constexpr int MOD = 1000000007;
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        //注意会因为浮点数导致少一个 size需要+1 或者直接 if (power > n) break;
        for (int i = 2; ; ++i) {
            int power = static_cast<int>(std::pow(i, x));
            if (power > n) break;
            for (int j = n; j >= power; --j) {
                dp[j] = (dp[j] + dp[j - power]) % MOD;
            }
        }
        return dp[n];
    }
};
#endif //SOLUTION_3_1_H
